package com.clei.algorithm.other;

import com.clei.utils.PrintUtil;

/**
 * 编辑距离
 * 题目描述：
 * <p>
 * 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
 * 你可以对一个单词进行如下三种操作：
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 * 示例1：
 * <p>
 * 输入: word1 = "horse", word2 = "ros"
 * 输出: 3
 * 解释:
 * horse -> rorse (将 'h' 替换为 'r')
 * rorse -> rose (删除 'r')
 * rose -> ros (删除 'e')
 * 示例2：
 * <p>
 * 输入: word1 = "intention", word2 = "execution"
 * 输出: 5
 * 解释:
 * intention -> inention (删除 't')
 * inention -> enention (将 'i' 替换为 'e')
 * enention -> exention (将 'n' 替换为 'x')
 * exention -> exection (将 'n' 替换为 'c')
 * exection -> execution (插入 'u')
 *
 * @author Y
 * @date 2022-12-16
 */
public class EditDistance {


    public static void main(String[] args) {
        PrintUtil.println(getMinEditDistance("aabcd", "bcd"));
    }

    /**
     * 获取最小编辑距离
     * 使用了动态规划
     *
     * @param str1 字符串1
     * @param str2 字符串2
     * @return 最小编辑距离
     */
    private static int getMinEditDistance(String str1, String str2) {
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        // 矩阵
        int x = arr2.length + 1;
        int y = arr1.length + 1;
        int[][] matrix = new int[x][y];
        for (int i = 1; i < x; i++) {
            matrix[i][0] = i;
        }
        for (int i = 1; i < y; i++) {
            matrix[0][i] = i;
        }
        for (int i = 1; i < x; i++) {
            for (int j = 1; j < y; j++) {
                int a = matrix[i - 1][j] + 1;
                int b = matrix[i][j - 1] + 1;
                int cost = arr1[j - 1] == arr2[i - 1] ? 0 : 1;
                int c = matrix[i - 1][j - 1] + cost;
                matrix[i][j] = Math.min(Math.min(a, b), c);

            }
        }
        // 打印矩阵
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                PrintUtil.print(matrix[i][j] + " ");
            }
            PrintUtil.println();
        }
        return matrix[x - 1][y - 1];
    }
}
